package com.captain.leetcode.回溯算法;

import java.util.*;

/**
 * @author captain
 * @Des 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 * <p>
 * 你可以按 任何顺序 返回答案。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 4, k = 2
 * 输出：
 * [
 * [2,4],
 * [3,4],
 * [2,3],
 * [1,2],
 * [1,3],
 * [1,4],
 * ]
 * 示例 2：
 * <p>
 * 输入：n = 1, k = 1
 * 输出：[[1]]
 * @Date 2021/8/4 0:36
 */
public class 组合77 {


    public static void main(String[] args) {
        List<List<Integer>> list = new 组合77().combine1(4, 2);
        list.stream().forEach(System.out::println);
    }

    public List<List<Integer>> combine(int n, int k) {
        //结果集合
        List<List<Integer>> res = new ArrayList<>();
        if (k <= 0 || n < k) {
            return res;
        }
        //记录层级关系
        Deque<Integer> path = new ArrayDeque<>();
        //递归往下
        dfs(n, k, 1, path, res);
        return res;
    }

    private void dfs(int n, int k, int index, Deque<Integer> path, List<List<Integer>> res) {
        //回溯条件
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 只有这里 i <= n - (k - path.size()) + 1 与参考代码 1 不同
        for (int i = index; i <= n - (k - path.size()) + 1; i++) {
            path.addLast(i);
            dfs(n, k, i + 1, path, res);
            path.removeLast();
        }

    }


    public List<List<Integer>> combine1(int n, int k) {
        //回溯核心递归  4大参数 1.返回值 2.开始集 3.开始位置 4.中间记录层级 qeque; 5.终止条件
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> path = new ArrayDeque<>();
        //记录层级深度
        dfs1(n, k, 1, path, res);
        return res;
    }

    //dfs

    private void dfs1(int n, int k, int begin, Deque<Integer> path, List<List<Integer>> res) {
        //退出条件
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            //回溯
            return;
        }
        //从每一层中拿出一个数字
        //起点的最大位置 , 超过之后没有意义了 , 举例
        // 1 2 3 4 5选择 3 个  开始3的时候,只能选择4 5 , 4的时候,没有任何意义了
        //n = 5 k = 3 path.size = 0  5 - 3 +1 = 4 最大为4时, 没有意义
        int maxSize = k - path.size();
        for (int i = begin; i <= n - maxSize + 1; i++) {
            path.add(i);
            //进入下一层,并往后遍历
            dfs1(n, k, i + 1, path, res);
            //结束循环
            path.removeLast();
        }
    }
}
